/************** Guangxi *****************/

#include "Route.h"
#include "contest_dm.h"
#include "RoutingBoundary.h"
#include <iostream>
#include <typeinfo>
#include <string>
#include <chrono>
#include "contest_util.h"

// 构造函数实现
namespace ieda_contest {

Route::Route(ContestDataManager* data_manager) {
    _data_manager = data_manager;
    // 建立unorder map便于检索
    _net_Map = buildNetPointMap();
}

// 路由处理函数实现
void Route::processRoute() {
    // 这里实现路由处理的逻辑
    // 例如，调用 DataManager 的方法或直接操作 DataManager 的数据
    int a = 1000;
    std::cout << a << std::endl;
}

void Route::addNetLength() {
    int single_gcell_x_span = _data_manager->get_database()->get_single_gcell_x_span();
    int single_gcell_y_span = _data_manager->get_database()->get_single_gcell_y_span();
    for (ContestNet& contest_net : _data_manager->get_database()->get_net_list()) {
        long long netLength = 0;
        for (ContestSegment& contest_segment : contest_net.get_routing_segment_list()) {
            netLength = netLength + contest_segment.getSegmentLength(single_gcell_x_span, single_gcell_y_span);
        }
        contest_net.set_net_length(netLength);
        // std::cout << "netLength: " << netLength << std::endl;
    }
}

std::unordered_map<std::string, ContestNet *> Route::buildNetPointMap() {
    std::unordered_map<std::string, ContestNet *> _netMap;

    for (ContestNet& contest_net : _data_manager->get_database()->get_net_list()) {
        // std::cout << "Adding net: " << contest_net.get_net_name() << std::endl;
        _netMap[contest_net.get_net_name()] = &contest_net;
        // std::cout << "_netMap size: " << _netMap.size() << std::endl;
    }
    
    return _netMap;
};

bool Route::isReroute(ContestNet *SingNetPtr) {
    auto& pins = SingNetPtr->get_pin_list();

    // 跳过空的引脚列表
    if (pins.empty()) {
        std::cout << "No pin in net: " << SingNetPtr->get_net_name() << std::endl;
        return false;
    }

    // 获取第一个引脚的坐标
    int first_pin_x = pins[0].get_grid_coord().get_x();
    int first_pin_y = pins[0].get_grid_coord().get_y();
    int first_pin_layer = pins[0].get_grid_coord().get_layer_idx();

    // 检查是否有不同网格坐标的引脚
    bool hasDifferentCoord = false;
    for (ContestPin& pin : pins) {


        if ((pin.get_grid_coord().get_x() != first_pin_x) ||
            (pin.get_grid_coord().get_y() != first_pin_y) ||
            ((pin.get_grid_coord().get_x() == first_pin_x &&
            pin.get_grid_coord().get_y() == first_pin_y) &&
            pin.get_grid_coord().get_layer_idx() != first_pin_layer)) {
            hasDifferentCoord = true;
            break;
        }
    }
    return hasDifferentCoord;
}

void Route::removeNet(ContestNet *SingNetPtr) {
    // 1. 移除网线辅助函数
    auto tryRemoveNet = [&](int x_coord, int y_coord, int layer_index) {
        // 2.1 找到对应x, y和layer index所在的GCell 
        SingleGcellInfo& cell = FindCellInMap(x_coord, y_coord, layer_index);
        // 2.2 判断一次这个cell是不是overflow，得到一个bool值
        bool flag1 = cell.isCellOverflow();
        // 2.3 判断一次，假设移除掉这个net，cell是不是overflow，得到一个bool值
        cell.addDemand(-1);
        bool flag2 = cell.isCellOverflow();
        // 2.4 如果两次bool值能表达刚开始overflow，然后移除之后不overflow了，则把这个Gcell记录下来
        if (flag1 && !flag2) {
            //std::unordered_set<ContestCoord>& OverflowGridsList = get_Overflow_Gcell_List();
            RemoveElementInOverflowGridsList(cell.get_cell_coord());
        }
        // 2.5 把2.3中假设移除的net加回去（不确定需不需要）
        // cell.addDemand(1);
    };

    // 3. 处理网线的引脚，ieda不需要
    // for (ContestPin &Pin : SingNetPtr->get_pin_list()) {
    //     int x_coord = Pin.get_grid_coord().get_x();
    //     int y_coord = Pin.get_grid_coord().get_y();
    //     int layer_index = Pin.get_grid_coord().get_layer_idx();
    //     tryRemoveNet(x_coord, y_coord, layer_index);
    // }    

    // 4. 更新总成本
    // 这里cost有变化吗？
    // auto Iter = _net_Map.find(SingNetPtr->get_net_name());
    // set_currentCost(Iter->second->get_net_length());

    // 5. 处理网线的布线路径
    for (ContestSegment &Segment : SingNetPtr->get_routing_segment_list()) {

        int lb_x = Segment.get_first().get_x();
        int lb_y = Segment.get_first().get_y();
        int lb_layer_idx = Segment.get_first().get_layer_idx();

        int rt_x = Segment.get_second().get_x();
        int rt_y = Segment.get_second().get_y();
        int rt_layer_idx = Segment.get_second().get_layer_idx();

        if (lb_layer_idx != rt_layer_idx) {
            continue;
        }

        for (int x_coord = Segment.get_first().get_x(); x_coord <= Segment.get_second().get_x(); x_coord++) {
            for (int y_coord = Segment.get_first().get_y(); y_coord <= Segment.get_second().get_y(); y_coord++) {
                for (int layer_index = Segment.get_first().get_layer_idx(); layer_index <= Segment.get_second().get_layer_idx(); layer_index++) {
                    if ((lb_x != rt_x && (x_coord == lb_x || x_coord == rt_x)) || (lb_y != rt_y && (y_coord == lb_y || y_coord == rt_y))) {
                    continue;
                    }
                    tryRemoveNet(x_coord, y_coord, layer_index);
                }
            }
        }
    }

}

void Route::addNet(ContestNet *SingNetPtr) {
    // 1. 添加网线辅助函数
    auto tryAddNet = [&](int x_coord, int y_coord, int layer_index) {
    // TODO: 实现 tryRemoveNet 的功能
        // 2.1 找到对应x, y和layer index所在的GCell 
        SingleGcellInfo& cell = FindCellInMap(x_coord, y_coord, layer_index);
        // 2.2 判断一次这个cell是不是overflow，得到一个bool值
        bool flag1 = cell.isCellOverflow();
        // 2.3 判断一次，假设增加一条net，cell是不是overflow，得到一个bool值
        cell.addDemand(1);
        bool flag2 = cell.isCellOverflow();
        // 2.4 如果两次bool值能表达刚开始没有overflow，但是增加之后overflow了，则把这个Gcell记录下来
        if (!flag1 && flag2) {
            // std::unordered_set<ContestCoord>& OverflowGridsList = get_Overflow_Gcell_List();
            addElementInOverflowGridsList(cell.get_cell_coord());
        }
        // 2.5 把2.3中假设增加的net减回去（不确定需不需要）
        // cell.addDemand(-1);
    };

    // 3. 处理网线的引脚，ieda不需要
    // for (ContestPin &Pin : SingNetPtr->get_pin_list()) {
    //     int x_coord = Pin.get_grid_coord().get_x();
    //     int y_coord = Pin.get_grid_coord().get_y();
    //     int layer_index = Pin.get_grid_coord().get_layer_idx();
    //     tryAddNet(x_coord, y_coord, layer_index);
    // }    

    // 4. 更新总成本
    // auto Iter = _net_Map.find(SingNetPtr->get_net_name());
    // set_currentCost(Iter->second->get_net_length());

    // 5. 处理网线的布线路径
    for (ContestSegment &Segment : SingNetPtr->get_routing_segment_list()) {

        int lb_x = Segment.get_first().get_x();
        int lb_y = Segment.get_first().get_y();
        int lb_layer_idx = Segment.get_first().get_layer_idx();

        int rt_x = Segment.get_second().get_x();
        int rt_y = Segment.get_second().get_y();
        int rt_layer_idx = Segment.get_second().get_layer_idx();

        if (lb_layer_idx != rt_layer_idx) {
            continue;
        }

        for (int x_coord = Segment.get_first().get_x(); x_coord <= Segment.get_second().get_x(); x_coord++) {
            for (int y_coord = Segment.get_first().get_y(); y_coord <= Segment.get_second().get_y(); y_coord++) {
                for (int layer_index = Segment.get_first().get_layer_idx(); layer_index <= Segment.get_second().get_layer_idx(); layer_index++) {
                    if ((lb_x != rt_x && (x_coord == lb_x || x_coord == rt_x)) || (lb_y != rt_y && (y_coord == lb_y || y_coord == rt_y))) {
                    continue;
                    }
                    tryAddNet(x_coord, y_coord, layer_index);
                }
            }
        }
    }

}

SingleGcellInfo& Route::FindCellInMap(int x, int y, int layerID) {

  ContestCoord coord(x, y, layerID);
  auto& contest_singleGcell_map = _data_manager->get_database()->get_singleGcell_map();

  // 在map中查找coord
  auto it = contest_singleGcell_map.find(coord);
  if (it != contest_singleGcell_map.end()) {
      // 如果找到了对应的SingleGcellInfo对象，返回这个对象的引用
      return it->second;
  } else {
      // 如果没有找到，抛出一个异常
      throw std::runtime_error("No SingleGcell found at the specified coordinates.");
  }
}

std::pair<std::vector<ContestSegment>, bool>
Route::singleNetRoute(ContestNet *SingNetPtr, std::vector<ContestSegment> &OriginRoute) {
    BoundaryBuilder buildBound(_data_manager, SingNetPtr, OriginRoute);
    RoutingGraphManager RGM(_data_manager);
    // TODO: 步骤1 - 创建可能的重新路由区域边界
    buildBound.createBoundaryInfo();
    if (!buildBound.isBoundaryInfoExist())
        return {{}, false};
    auto BoundaryInfo = buildBound.getBoundaryInfo();
    RGM.setBoundaryInfor(&BoundaryInfo);
    // TODO: 步骤2 - 生成无向图
    RGM.createGraph(RGM.getLayerFactor(0), RGM.getLayerDir());
    const auto &G = RGM.get_SteinerTree();

    // TODO: 步骤3 - 使用第三方最短路径求解器进行重新路由
    steiner_tree::Solver<long long> Solver(G);
    auto Res = Solver.solve(BoundaryInfo.get_terminals());
    if (!Res) {
        return {{}, false};
    }
    // TODO: 步骤4 - 生成最终路由基于求解器的结果
    auto FinalRoute = RGM.createFinalRoute(*Res, SingNetPtr);

    // TODO: 步骤五，判断生成的线是否有连接问题, 根据具体实现返回最终路由或失败标志
    bool flag = SingleNetConnectivity(SingNetPtr->get_pin_list(), FinalRoute, SingNetPtr->get_net_name());
    if (flag) {
        return {FinalRoute, true};
    } else {
        return {{}, false};
    }

    // TODO:
    // return {FinalRoute, true};
}

void Route::reduceRouteSegments(std::vector<ContestSegment> &RoutingSegments) {
    //int guangxi = 1;
    auto RouteSegmentCmp = [&](ContestSegment &A, ContestSegment &B) {
        // Horizontal or Vertical or Via
        auto TA = getType(A);
        auto TB = getType(B);
        if (TA != TB)
            return TA < TB;

        if (TA == Type::Horizontal) {
            if (A.get_first().get_layer_idx() != B.get_first().get_layer_idx())
                return A.get_first().get_layer_idx() < B.get_first().get_layer_idx();
            if (A.get_first().get_y() != B.get_first().get_y()) 
                return A.get_first().get_y() < B.get_first().get_y();
            return A.get_first().get_x() < B.get_first().get_x();
        } else if (TA == Type::Vertical) {
            if (A.get_first().get_layer_idx() != B.get_first().get_layer_idx())
                return A.get_first().get_layer_idx() < B.get_first().get_layer_idx();
            if (A.get_first().get_x() != B.get_first().get_x()) 
                return A.get_first().get_x() < B.get_first().get_x();
            return A.get_first().get_y() < B.get_first().get_y();
        } else if (TA == Type::Via) {
            if (A.get_first().get_y() != B.get_first().get_y()) 
                return A.get_first().get_y() < B.get_first().get_y();
            if (A.get_first().get_x() != B.get_first().get_x()) 
                return A.get_first().get_x() < B.get_first().get_x();
            return A.get_first().get_layer_idx() < B.get_first().get_layer_idx();
        } else {
            assert(false && "Error RouteSegment::Type!");
        }
    };

    // Sort Routed Segment
    std::sort(RoutingSegments.begin(), RoutingSegments.end(), RouteSegmentCmp);
    // Generate NewRouteSegments by RouteSegments
    std::vector<ContestSegment> NewRouteSegments;
    ContestSegment *CurRS = nullptr;

    // For each RouteSegment
    for (auto &RS : RoutingSegments) {
        bool NeedsNewRS = false;
        auto Ty = getType(RS);
        // 检查当前segment RS的类型与前一个segment CurRS的类型是否相同，
        // 如果CurRS为nullptr（即RS是第一个路由段）或者类型不同，则需要新的路由段。
        if (CurRS == nullptr || Ty != getType(*CurRS)) {
            NeedsNewRS = true;
        } else {
            bool Y_cmp = CurRS->get_first().get_y() == RS.get_first().get_y();
            bool X_cmp = CurRS->get_first().get_x() == RS.get_first().get_x();
            bool Via_cmp = CurRS->get_first().get_layer_idx() == RS.get_first().get_layer_idx();
            if (X_cmp && Y_cmp && Via_cmp) continue; // Identical Routing Segment

            if (Ty == Type::Horizontal) {
                // If in Horizontal Layor
                // If Current Routing Segment's ending x position equals RS's starting x position
                // We can Reduce Route Segment
                if (Y_cmp && Via_cmp && CurRS->get_second().get_x() == RS.get_first().get_x()) {
                    CurRS->get_second().set_x(RS.get_second().get_x());
                    int x_coord = CurRS->get_second().get_x();
                    int y_coord = CurRS->get_second().get_y();
                    int L_coord = CurRS->get_second().get_layer_idx();
                    ContestCoord tmp_coord(x_coord, y_coord, L_coord);
                    CurRS->set_second(tmp_coord);
                } else {
                    NeedsNewRS = true;
                }
            } else if (Ty == Type::Vertical) {
                // If in Vertical Layor
                // If Current Routing Segment's ending y position equals RS's starting y position
                // We can Reduce Route Segment
                if (X_cmp && Via_cmp && CurRS->get_second().get_y() == RS.get_first().get_y()) {
                    int x_coord = CurRS->get_second().get_x();
                    CurRS->get_second().set_y(RS.get_second().get_y());
                    int y_coord = CurRS->get_second().get_y();
                    int L_coord = CurRS->get_second().get_layer_idx();
                    ContestCoord tmp_coord(x_coord, y_coord, L_coord);
                    CurRS->set_second(tmp_coord);
                } else {
                    NeedsNewRS = true;
                }
            } else if (Ty == Type::Via) {
                // If Current Routing Segment's ending layer position equals RS's starting layor position
                // We can Reduce Route Segment
                if (X_cmp && Y_cmp && CurRS->get_second().get_layer_idx() == RS.get_first().get_layer_idx()) {
                    int x_coord = CurRS->get_second().get_x();
                    int y_coord = CurRS->get_second().get_y();
                    CurRS->get_second().set_y(RS.get_second().get_layer_idx());
                    int L_coord = CurRS->get_second().get_layer_idx();
                    ContestCoord tmp_coord(x_coord, y_coord, L_coord);
                    CurRS->set_second(tmp_coord);
                } else {
                    NeedsNewRS = true;
                }
            } else {
                NeedsNewRS = true;
            }
        }

        if (NeedsNewRS) {
            if (CurRS)
                NewRouteSegments.emplace_back(*CurRS);
            CurRS = &RS;
        }
    }

    if (CurRS) {
        NewRouteSegments.emplace_back(*CurRS);
    }
    // update the routing segment vector
    RoutingSegments = std::move(NewRouteSegments);

}

long long Route::get_newCost(std::vector<ContestSegment> &RoutingSegment) {
    int single_gcell_x_span = _data_manager->get_database()->get_single_gcell_x_span();
    int single_gcell_y_span = _data_manager->get_database()->get_single_gcell_y_span();
    long long netLength = 0;
    for (ContestSegment& contest_segment : RoutingSegment) {
        netLength = netLength + contest_segment.getSegmentLength(single_gcell_x_span, single_gcell_y_span);
    }
    return netLength;
}

void Route::initialCurrentCost() {
    int single_gcell_x_span = _data_manager->get_database()->get_single_gcell_x_span();
    int single_gcell_y_span = _data_manager->get_database()->get_single_gcell_y_span();
    long long totalNetLength = 0;
    for (ContestNet& contest_net : _data_manager->get_database()->get_net_list()) {
        // for (ContestSegment& contest_segment : contest_net.get_routing_segment_list()) {
        //     totalNetLength = totalNetLength + contest_segment.getSegmentLength(single_gcell_x_span, single_gcell_y_span);
        //     std::cout << "totalNetLength: " << totalNetLength << std::endl;
        // }
        totalNetLength = totalNetLength + contest_net.get_net_length();
        // std::cout << "totalNetLength: " << totalNetLength << std::endl;
    }
    set_currentCost(totalNetLength);
}

void Route::rerouteAll() {

    // 获取函数开始时的时间
    auto start_time = std::chrono::high_resolution_clock::now();

    // auto net_Map = buildNetPointMap();
    // 建立一个空的向量pair
    std::vector<std::pair<ContestNet *, long long>> NetPtrs;

    // Cost for Net reroute order: net_length * num_pins
    // 遍历_net_Map中的每一个元素
    for (auto &my_net_map : _net_Map) {
        NetPtrs.emplace_back(my_net_map.second, my_net_map.second->get_net_length() * my_net_map.second->get_pin_list().size());
    }

    // Sorting，按一定规则排序， net_length * num_pins大的放前面
    // 由于iEDA中 只要在一个gcell里面，就默认连接上了，所以会出现很多net_length * num_pins是0的情况
    auto NetCmp =
    [&](std::pair<ContestNet *, long long> &A,
        std::pair<ContestNet *, long long> &B) {

    return A.second > B.second;
    
    };

    std::sort(NetPtrs.begin(), NetPtrs.end(), NetCmp);

    // for loop，遍历每一条NetPtrs中的每一个元素，第一个是net的指针，第二个是net_length * num_pins
    int guangxi_count = 1; // 测试SingeNetRoute的速度用的变量，之后删除
    for (auto &P : NetPtrs)  {

        // 在循环的每一步检查时间
        auto current_time = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::seconds>(current_time - start_time).count();

        // 如果已经超过 3300 秒（即 55 分钟），就退出循环
        if (duration >= 3300) {
            std::cout << "Time limit of 55 mins exceeded. Exiting loop." << std::endl;
            break;
        }

        auto SingNetPtr = P.first;
        // 获取原始布线
        auto &OriginRoute = _net_Map[SingNetPtr->get_net_name()]->get_routing_segment_list();

        // 测试SingeNetRoute的速度用的变量，之后删除
        // std::cout << "Current Net Number: " << guangxi_count << std::endl;
        //std::cout << "Number of Routing Segment: " << SingNetPtr->get_routing_segment_list().size() << std::endl;
        //std::cout << "Number of Pin: " << SingNetPtr->get_pin_list().size() << std::endl;
        guangxi_count++;
        // std::string tnet = "FE_OFN1644_n87518";
        if (!isReroute(SingNetPtr)) {
            //std::cout << "All pins in the same GCell or no pin in the net: " << SingNetPtr->get_net_name() << std::endl;
            continue;
        }
        else {
            if (guangxi_count % 3000 == 0) {
                std::cout << "Current Net Number: " << guangxi_count << std::endl;
                std::cout << "Do Net Reroute, Exist pins in different Gcell: " << SingNetPtr->get_net_name() << std::endl;
            }
            // 4. Remove Net in sorted vector
            removeNet(SingNetPtr);

            // 5. Route Single Net
            std::vector<ContestSegment> newRoute = singleNetRoute(SingNetPtr, OriginRoute).first;

            // 6. Further Reduce Redundant Routing Segments
            // reduceRouteSegments(newRoute);  // 暂时注释掉，via部分有代码bug，会导致短线，对结果没有影响。
            ///////////// 一个测试 检测原始布线和新布线的坐标有没有变化 /////////////////////
            // for (ContestSegment originSegment : OriginRoute) {
            //     ContestCoord coord_start = originSegment.get_first();
            //     ContestCoord coord_end = originSegment.get_second();
            //     std::cout << "Start Points of Original Routing Segment: x = " << coord_start.get_x() 
            //     << ", y = " << coord_start.get_y() << ", L = " << coord_start.get_layer_idx() << std::endl;
            //     std::cout << "End Points of Original Routing Segment: x = " << coord_end.get_x() 
            //     << ", y = " << coord_end.get_y() << ", L = " << coord_end.get_layer_idx() << std::endl;
            // }
            // std::cout << " " << std::endl;
            // for (ContestSegment newSegment : newRoute) {
            //     ContestCoord coord_start = newSegment.get_first();
            //     ContestCoord coord_end = newSegment.get_second();
            //     std::cout << "Start Points of New Routing Segment: x = " << coord_start.get_x() 
            //     << ", y = " << coord_start.get_y() << ", L = " << coord_start.get_layer_idx() << std::endl;
            //     std::cout << "End Points of Original Routing Segment: x = " << coord_end.get_x() 
            //     << ", y = " << coord_end.get_y() << ", L = " << coord_end.get_layer_idx() << std::endl;
            // }
            ////////////////// 测试完成 ///////////////////////////////////
            
            // 6.1 Figure out cost of original routing
            int routingCost_1 = SingNetPtr->get_net_length();
            // 6.2 Figure out cost of new routing
            int routingCost_2 = get_newCost(newRoute);
            // std::cout << "***************************" << std::endl;
            // std::cout << "Routing net number: " << guangxi_count << std::endl;
            // std::cout << "Original Cost: " << routingCost_1 << std::endl;
            // std::cout << "New Cost: " << routingCost_2 << std::endl;
            // std::cout << "Total Cost: " << get_currentCost() << std::endl;
            // std::cout << "***************************" << std::endl;
            // 6.3 update or not
            if (routingCost_2 < routingCost_1) {
                // std::string testingNet = "n64616";
                // std::cout << "Original Route" << std::endl;
                // for (ContestSegment originSegment : _net_Map[SingNetPtr->get_net_name()]->get_routing_segment_list()) {
                //     ContestCoord coord_start = originSegment.get_first();
                //     ContestCoord coord_end = originSegment.get_second();
                //     std::cout << "Start Points of Original Routing Segment: x = " << coord_start.get_x() 
                //     << ", y = " << coord_start.get_y() << ", L = " << coord_start.get_layer_idx() << std::endl;
                //     std::cout << "End Points of Original Routing Segment: x = " << coord_end.get_x() 
                //     << ", y = " << coord_end.get_y() << ", L = " << coord_end.get_layer_idx() << std::endl;
                // }
                // std::cout << "Original Route in DataManager" << std::endl;
                // for (ContestNet& netTesting : _data_manager->get_database()->get_net_list()) {
                //     if (netTesting.get_net_name() == testingNet) {
                //         for (ContestSegment originSegment : netTesting.get_routing_segment_list()) {
                //             ContestCoord coord_start = originSegment.get_first();
                //             ContestCoord coord_end = originSegment.get_second();
                //             std::cout << "Start Points of Original Routing Segment: x = " << coord_start.get_x() 
                //             << ", y = " << coord_start.get_y() << ", L = " << coord_start.get_layer_idx() << std::endl;
                //             std::cout << "End Points of Original Routing Segment: x = " << coord_end.get_x() 
                //             << ", y = " << coord_end.get_y() << ", L = " << coord_end.get_layer_idx() << std::endl;
                //         }
                //     }
                // }

                OriginRoute = std::move(newRoute);
                // std::cout << "Afther Route" << std::endl;
                // for (ContestSegment originSegment : _net_Map[SingNetPtr->get_net_name()]->get_routing_segment_list()) {
                //     ContestCoord coord_start = originSegment.get_first();
                //     ContestCoord coord_end = originSegment.get_second();
                //     std::cout << "Start Points of Original Routing Segment: x = " << coord_start.get_x() 
                //     << ", y = " << coord_start.get_y() << ", L = " << coord_start.get_layer_idx() << std::endl;
                //     std::cout << "End Points of Original Routing Segment: x = " << coord_end.get_x() 
                //     << ", y = " << coord_end.get_y() << ", L = " << coord_end.get_layer_idx() << std::endl;
                // }
                // std::cout << "Afther Route in DataManager" << std::endl;
                // for (ContestNet& netTesting : _data_manager->get_database()->get_net_list()) {
                //     if (netTesting.get_net_name() == testingNet) {
                //         for (ContestSegment originSegment : netTesting.get_routing_segment_list()) {
                //             ContestCoord coord_start = originSegment.get_first();
                //             ContestCoord coord_end = originSegment.get_second();
                //             std::cout << "Start Points of Original Routing Segment: x = " << coord_start.get_x() 
                //             << ", y = " << coord_start.get_y() << ", L = " << coord_start.get_layer_idx() << std::endl;
                //             std::cout << "End Points of Original Routing Segment: x = " << coord_end.get_x() 
                //             << ", y = " << coord_end.get_y() << ", L = " << coord_end.get_layer_idx() << std::endl;
                //         }
                //     }
                // }

                // SingNetPtr->set_routing_segment_list(OriginRoute);
                SingNetPtr->set_net_length(routingCost_2);
                set_currentCost(routingCost_2 - routingCost_1);
                // SingNetPtr->set_guide_list()
                std::cout << "Performance Improvement: " << SingNetPtr->get_net_name() << std::endl;

                // 修改datamanager的对应net的guide list
                std::map<int, std::string>& layer_idx_to_name_map = _data_manager->get_database()->get_layer_idx_to_name_map();
                int single_gcell_x_span = _data_manager->get_database()->get_single_gcell_x_span();
                int single_gcell_y_span = _data_manager->get_database()->get_single_gcell_y_span();
                std::vector<ContestGuide> newGuide;
                for (ContestSegment NewSegment : OriginRoute) {

                    int real_lb_x = NewSegment.get_first().get_x() * single_gcell_x_span + 1 - (single_gcell_x_span / 2);
                    int real_lb_y = NewSegment.get_first().get_y() * single_gcell_y_span + 1 - (single_gcell_y_span / 2);
                    std::string real_lb_layer_name = layer_idx_to_name_map[NewSegment.get_first().get_layer_idx()];

                    int real_rt_x = NewSegment.get_second().get_x() * single_gcell_x_span + 1 + (single_gcell_x_span / 2);
                    int real_rt_y = NewSegment.get_second().get_y() * single_gcell_y_span + 1 + (single_gcell_y_span / 2);
                    std::string real_rt_layer_name = layer_idx_to_name_map[NewSegment.get_second().get_layer_idx()];

                    if (real_rt_layer_name == real_lb_layer_name) {
                        ContestGuide tmp_guide;
                        tmp_guide.set_lb_x(real_lb_x);
                        tmp_guide.set_lb_y(real_lb_y);
                        tmp_guide.set_rt_x(real_rt_x);
                        tmp_guide.set_rt_y(real_rt_y);
                        tmp_guide.set_layer_name(real_rt_layer_name);
                        newGuide.push_back(tmp_guide);
                    } else {
                        ContestGuide tmp_guide1;
                        tmp_guide1.set_lb_x(real_lb_x);
                        tmp_guide1.set_lb_y(real_lb_y);
                        tmp_guide1.set_rt_x(real_rt_x);
                        tmp_guide1.set_rt_y(real_rt_y);
                        tmp_guide1.set_layer_name(real_lb_layer_name);
                        newGuide.push_back(tmp_guide1);

                        ContestGuide tmp_guide2;
                        tmp_guide2.set_lb_x(real_lb_x);
                        tmp_guide2.set_lb_y(real_lb_y);
                        tmp_guide2.set_rt_x(real_rt_x);
                        tmp_guide2.set_rt_y(real_rt_y);
                        tmp_guide2.set_layer_name(real_rt_layer_name);
                        newGuide.push_back(tmp_guide2);
                    }
                }

                SingNetPtr->set_guide_list(newGuide);

            }

            // 7. Add Net back
            addNet(SingNetPtr);

            // 8. 测试代码
            // if (guangxi_count > 120000) {
            //     break;
            // }
        } 
    }
}

std::map<int, idb::IdbLayerDirection>& RoutingGraphManager::getLayerDir() {
  _layer_idx_to_direction_map = _data_manager->get_database()->get_layer_idx_to_direction_map();
  return _layer_idx_to_direction_map;
}

std::vector<int>& RoutingGraphManager::getLayerFactor(int powerFactor) {
  int total_routing_layer = _data_manager->get_idb_layout()->get_layers()->get_routing_layers_number();
  _LayerFactor.clear();
  _LayerFactor.resize(total_routing_layer, powerFactor);
  return _LayerFactor;
}

void RoutingGraphManager::createGraph(const std::vector<int>& LayerFactor,
                                      const std::map<int, idb::IdbLayerDirection>& layer_idx_to_direction_map) {
  //int guangxi = 1;
  Route Route_tmp(_data_manager);
  steiner_tree::UndirectedGraph<long long>& G = get_SteinerTree();
  G.clear();
  auto &Codec = get_BoundaryInfo()->get_CodeC();
  G.setVertexNum(Codec.max());

  // 1. 从BoundaryInfo里面抽取边界信息
  RoutingBoundaryInfo* BoundaryInfo_tmp = get_BoundaryInfo();
  int Min_X = BoundaryInfo_tmp->getStartCoordinate().get_x();
  int Min_Y = BoundaryInfo_tmp->getStartCoordinate().get_y();
  int Min_L = BoundaryInfo_tmp->getStartCoordinate().get_layer_idx();
  int Max_X = BoundaryInfo_tmp->getEndCoordinate().get_x();
  int Max_Y = BoundaryInfo_tmp->getEndCoordinate().get_y();
  int Max_L = BoundaryInfo_tmp->getEndCoordinate().get_layer_idx();

  // 2. 搜索可能需要布线的水平或者垂直segment
  for (int L = Min_L; L <= Max_L; L++) {
    // 2.1 水平部分
    if (layer_idx_to_direction_map.at(L) == idb::IdbLayerDirection::kHorizontal) {
        //std::cout << "kHorizontal" << L << std::endl;
        for (int X = Min_X; X < Max_X; X++) {
            for (int Y = Min_Y; Y <= Max_Y; Y++) {
                SingleGcellInfo& grid_tmp_1 = Route_tmp.FindCellInMap(X, Y, L);
                SingleGcellInfo& grid_tmp_2 = Route_tmp.FindCellInMap(X + 1, Y, L);
                int sp1 = grid_tmp_1.get_cell_supply();
                int sp2 = grid_tmp_2.get_cell_supply();
                if (sp1 <= 0 || sp2 <= 0) {
                    continue;
                }

                // 获取当前Gcell和邻接Gcell的坐标编码
                auto Coord = Codec.encode({
                    (unsigned long long)(X - Min_X),
                    (unsigned long long)(Y - Min_Y),
                    (unsigned long long)(L - Min_L)
                });

                auto NeiCoord = Codec.encode({
                    (unsigned long long)(X - Min_X + 1),
                    (unsigned long long)(Y - Min_Y),
                    (unsigned long long)(L - Min_L)
                });

                // 定义routing segment的cost函数
                long long cap_v1 = grid_tmp_1.get_cell_supply();
                long long cap_v2 = grid_tmp_2.get_cell_supply();
                long long op_v = 0;
                if (cap_v1 <= 0 || cap_v2 <= 0) op_v = INT_MAX; 
                long long weight = LayerFactor.at(L) * 2 + op_v + (cap_v1 + cap_v2) / 2;

                G.addEdge(Coord, NeiCoord, weight);
            }
        }
    }
    // 2.2 垂直部分
    if (layer_idx_to_direction_map.at(L) == idb::IdbLayerDirection::kVertical) {
        //std::cout << "kVertical" << L << std::endl;
        for (int X = Min_X; X <= Max_X; X++) {
            for (int Y = Min_Y; Y < Max_Y; Y++) {
                SingleGcellInfo& grid_tmp_1 = Route_tmp.FindCellInMap(X, Y, L);
                SingleGcellInfo& grid_tmp_2 = Route_tmp.FindCellInMap(X, Y + 1, L);
                int sp1 = grid_tmp_1.get_cell_supply();
                int sp2 = grid_tmp_2.get_cell_supply();
                if (sp1 <= 0 || sp2 <= 0) {
                    continue;
                }

                // 获取当前Gcell和邻接Gcell的坐标编码
                auto Coord = Codec.encode({
                    (unsigned long long)(X - Min_X),
                    (unsigned long long)(Y - Min_Y),
                    (unsigned long long)(L - Min_L)
                });

                auto NeiCoord = Codec.encode({
                    (unsigned long long)(X - Min_X),
                    (unsigned long long)(Y - Min_Y + 1),
                    (unsigned long long)(L - Min_L)
                });

                // 定义routing segment的cost函数
                long long cap_v1 = grid_tmp_1.get_cell_supply();
                long long cap_v2 = grid_tmp_2.get_cell_supply();
                long long op_v = 0;
                if (cap_v1 <= 0 || cap_v2 <= 0) op_v = INT_MAX; 
                long long weight = LayerFactor.at(L) * 2 + op_v + (cap_v1 + cap_v2) / 2;

                G.addEdge(Coord, NeiCoord, weight);
            }
        }
    }
  }

  // 3. 搜索可能需要布线的via segment
  for (int L = Min_L; L < Max_L; L++) {
    for (int X = Min_X; X <= Max_X; X++) {
        for (int Y = Min_Y; Y <= Min_Y; Y++) {

            SingleGcellInfo& grid_tmp_1 = Route_tmp.FindCellInMap(X, Y, L);
            SingleGcellInfo& grid_tmp_2 = Route_tmp.FindCellInMap(X, Y, L + 1);
            int sp1 = grid_tmp_1.get_cell_supply();
            int sp2 = grid_tmp_2.get_cell_supply();
            if (sp1 <= 0 || sp2 <= 0) {
                continue;
            }

            // 获取当前Gcell和邻接Gcell的坐标编码
            auto Coord = Codec.encode({
                (unsigned long long)(X - Min_X),
                (unsigned long long)(Y - Min_Y),
                (unsigned long long)(L - Min_L)
            });

            auto NeiCoord = Codec.encode({
                (unsigned long long)(X - Min_X),
                (unsigned long long)(Y - Min_Y),
                (unsigned long long)(L - Min_L + 1)
            });

            // 定义Via segment的cost
            long long Weight = LayerFactor.at(L) + LayerFactor.at(L + 1);

            G.addEdge(Coord, NeiCoord, Weight);
        }
    }
  }

  //set_SteinerTree(G);

}



void RoutingGraphManager::createGraphV2(const std::vector<int>& LayerFactor,
                                      const std::map<int, idb::IdbLayerDirection>& layer_idx_to_direction_map) {
  //int guangxi = 1;
  Route Route_tmp(_data_manager);
  steiner_tree::UndirectedGraph<long long>& G = get_SteinerTree();
  G.clear();
  auto &Codec = get_BoundaryInfo()->get_CodeC();
  G.setVertexNum(Codec.max());

  // 1. 从BoundaryInfo里面抽取边界信息
  RoutingBoundaryInfo* BoundaryInfo_tmp = get_BoundaryInfo();
  int Min_X = BoundaryInfo_tmp->getStartCoordinate().get_x();
  int Min_Y = BoundaryInfo_tmp->getStartCoordinate().get_y();
  int Min_L = BoundaryInfo_tmp->getStartCoordinate().get_layer_idx();
  int Max_X = BoundaryInfo_tmp->getEndCoordinate().get_x();
  int Max_Y = BoundaryInfo_tmp->getEndCoordinate().get_y();
  int Max_L = BoundaryInfo_tmp->getEndCoordinate().get_layer_idx();

  for (int L = Min_L; L <= Max_L; L++) {
    for (int X = Min_X; X <= Max_X; X++) {
        for (int Y = Min_Y; Y <= Max_Y; Y++) {
            if (layer_idx_to_direction_map.at(L) == idb::IdbLayerDirection::kHorizontal) {
                if (X == Max_X) {
                    //continue;
                } else {
                    SingleGcellInfo& grid_tmp_1 = Route_tmp.FindCellInMap(X, Y, L);
                    SingleGcellInfo& grid_tmp_2 = Route_tmp.FindCellInMap(X + 1, Y, L);
                    int sp1 = grid_tmp_1.get_cell_supply();
                    int sp2 = grid_tmp_2.get_cell_supply();
                    if (sp1 <= 0 || sp2 <= 0) {
                        continue;
                    }

                    // 获取当前Gcell和邻接Gcell的坐标编码
                    auto Coord = Codec.encode({
                        (unsigned long long)(X - Min_X),
                        (unsigned long long)(Y - Min_Y),
                        (unsigned long long)(L - Min_L)
                    });

                    auto NeiCoord = Codec.encode({
                        (unsigned long long)(X - Min_X + 1),
                        (unsigned long long)(Y - Min_Y),
                        (unsigned long long)(L - Min_L)
                    });

                    // 定义routing segment的cost函数
                    long long cap_v1 = grid_tmp_1.get_cell_supply();
                    long long cap_v2 = grid_tmp_2.get_cell_supply();
                    long long op_v = 0;
                    if (cap_v1 <= 0 || cap_v2 <= 0) op_v = INT_MAX; 
                    long long weight = LayerFactor.at(L) * 2 + op_v + (cap_v1 + cap_v2) / 2;

                    G.addEdge(Coord, NeiCoord, weight);
                }
            } else if (layer_idx_to_direction_map.at(L) == idb::IdbLayerDirection::kVertical) {
                if (Y == Max_Y) {
                    //continue;
                } else {
                    SingleGcellInfo& grid_tmp_1 = Route_tmp.FindCellInMap(X, Y, L);
                    SingleGcellInfo& grid_tmp_2 = Route_tmp.FindCellInMap(X, Y + 1, L);
                    int sp1 = grid_tmp_1.get_cell_supply();
                    int sp2 = grid_tmp_2.get_cell_supply();
                    if (sp1 <= 0 || sp2 <= 0) {
                        continue;
                    }

                    // 获取当前Gcell和邻接Gcell的坐标编码
                    auto Coord = Codec.encode({
                        (unsigned long long)(X - Min_X),
                        (unsigned long long)(Y - Min_Y),
                        (unsigned long long)(L - Min_L)
                    });

                    auto NeiCoord = Codec.encode({
                        (unsigned long long)(X - Min_X),
                        (unsigned long long)(Y - Min_Y + 1),
                        (unsigned long long)(L - Min_L)
                    });

                    // 定义routing segment的cost函数
                    long long cap_v1 = grid_tmp_1.get_cell_supply();
                    long long cap_v2 = grid_tmp_2.get_cell_supply();
                    long long op_v = 0;
                    if (cap_v1 <= 0 || cap_v2 <= 0) op_v = INT_MAX; 
                    long long weight = LayerFactor.at(L) * 2 + op_v + (cap_v1 + cap_v2) / 2;

                    G.addEdge(Coord, NeiCoord, weight);
                }
            }

            if (L == Max_L) {
                //continue;
            } else {
                SingleGcellInfo& grid_tmp_1 = Route_tmp.FindCellInMap(X, Y, L);
                SingleGcellInfo& grid_tmp_2 = Route_tmp.FindCellInMap(X, Y, L + 1);
                int sp1 = grid_tmp_1.get_cell_supply();
                int sp2 = grid_tmp_2.get_cell_supply();
                if (sp1 <= 0 || sp2 <= 0) {
                    continue;
                }

                // 获取当前Gcell和邻接Gcell的坐标编码
                auto Coord = Codec.encode({
                    (unsigned long long)(X - Min_X),
                    (unsigned long long)(Y - Min_Y),
                    (unsigned long long)(L - Min_L)
                });

                auto NeiCoord = Codec.encode({
                    (unsigned long long)(X - Min_X),
                    (unsigned long long)(Y - Min_Y),
                    (unsigned long long)(L - Min_L + 1)
                });

                // 定义Via segment的cost
                long long Weight = LayerFactor.at(L) + LayerFactor.at(L + 1);

                G.addEdge(Coord, NeiCoord, Weight);
            }
        }
    }
  }

  // 2. 搜索可能需要布线的水平或者垂直segment
  for (int L = Min_L; L <= Max_L; L++) {
    // 2.1 水平部分
    if (layer_idx_to_direction_map.at(L) == idb::IdbLayerDirection::kHorizontal) {
        //std::cout << "kHorizontal" << L << std::endl;
        for (int X = Min_X; X < Max_X; X++) {
            for (int Y = Min_Y; Y <= Max_Y; Y++) {
                SingleGcellInfo& grid_tmp_1 = Route_tmp.FindCellInMap(X, Y, L);
                SingleGcellInfo& grid_tmp_2 = Route_tmp.FindCellInMap(X + 1, Y, L);
                int sp1 = grid_tmp_1.get_cell_supply();
                int sp2 = grid_tmp_2.get_cell_supply();
                if (sp1 <= 0 || sp2 <= 0) {
                    continue;
                }

                // 获取当前Gcell和邻接Gcell的坐标编码
                auto Coord = Codec.encode({
                    (unsigned long long)(X - Min_X),
                    (unsigned long long)(Y - Min_Y),
                    (unsigned long long)(L - Min_L)
                });

                auto NeiCoord = Codec.encode({
                    (unsigned long long)(X - Min_X + 1),
                    (unsigned long long)(Y - Min_Y),
                    (unsigned long long)(L - Min_L)
                });

                // 定义routing segment的cost函数
                long long cap_v1 = grid_tmp_1.get_cell_supply();
                long long cap_v2 = grid_tmp_2.get_cell_supply();
                long long op_v = 0;
                if (cap_v1 <= 0 || cap_v2 <= 0) op_v = INT_MAX; 
                long long weight = LayerFactor.at(L) * 2 + op_v + (cap_v1 + cap_v2) / 2;

                G.addEdge(Coord, NeiCoord, weight);
            }
        }
    }
    // 2.2 垂直部分
    if (layer_idx_to_direction_map.at(L) == idb::IdbLayerDirection::kVertical) {
        //std::cout << "kVertical" << L << std::endl;
        for (int X = Min_X; X <= Max_X; X++) {
            for (int Y = Min_Y; Y < Max_Y; Y++) {
                SingleGcellInfo& grid_tmp_1 = Route_tmp.FindCellInMap(X, Y, L);
                SingleGcellInfo& grid_tmp_2 = Route_tmp.FindCellInMap(X, Y + 1, L);
                int sp1 = grid_tmp_1.get_cell_supply();
                int sp2 = grid_tmp_2.get_cell_supply();
                if (sp1 <= 0 || sp2 <= 0) {
                    continue;
                }

                // 获取当前Gcell和邻接Gcell的坐标编码
                auto Coord = Codec.encode({
                    (unsigned long long)(X - Min_X),
                    (unsigned long long)(Y - Min_Y),
                    (unsigned long long)(L - Min_L)
                });

                auto NeiCoord = Codec.encode({
                    (unsigned long long)(X - Min_X),
                    (unsigned long long)(Y - Min_Y + 1),
                    (unsigned long long)(L - Min_L)
                });

                // 定义routing segment的cost函数
                long long cap_v1 = grid_tmp_1.get_cell_supply();
                long long cap_v2 = grid_tmp_2.get_cell_supply();
                long long op_v = 0;
                if (cap_v1 <= 0 || cap_v2 <= 0) op_v = INT_MAX; 
                long long weight = LayerFactor.at(L) * 2 + op_v + (cap_v1 + cap_v2) / 2;

                G.addEdge(Coord, NeiCoord, weight);
            }
        }
    }
  }

  // 3. 搜索可能需要布线的via segment
  for (int L = Min_L; L < Max_L; L++) {
    for (int X = Min_X; X <= Max_X; X++) {
        for (int Y = Min_Y; Y <= Min_Y; Y++) {

            SingleGcellInfo& grid_tmp_1 = Route_tmp.FindCellInMap(X, Y, L);
            SingleGcellInfo& grid_tmp_2 = Route_tmp.FindCellInMap(X, Y, L + 1);
            int sp1 = grid_tmp_1.get_cell_supply();
            int sp2 = grid_tmp_2.get_cell_supply();
            if (sp1 <= 0 || sp2 <= 0) {
                continue;
            }

            // 获取当前Gcell和邻接Gcell的坐标编码
            auto Coord = Codec.encode({
                (unsigned long long)(X - Min_X),
                (unsigned long long)(Y - Min_Y),
                (unsigned long long)(L - Min_L)
            });

            auto NeiCoord = Codec.encode({
                (unsigned long long)(X - Min_X),
                (unsigned long long)(Y - Min_Y),
                (unsigned long long)(L - Min_L + 1)
            });

            // 定义Via segment的cost
            long long Weight = LayerFactor.at(L) + LayerFactor.at(L + 1);

            G.addEdge(Coord, NeiCoord, Weight);
        }
    }
  }

  //set_SteinerTree(G);

}

std::vector<ContestSegment> 
RoutingGraphManager::createFinalRoute(const std::vector<size_t> &Eids, 
                                      const ContestNet *Net) {
    auto routingSegmentUnderMinL = std::move(get_BoundaryInfo()->routeUnderMinLaye());
    for (auto &EdgeIdx : Eids) {
        auto &Edge = get_SteinerTree().getEdge(EdgeIdx);

        auto Decode1 = get_BoundaryInfo()->get_CodeC().decode(Edge.v1);
        auto Decode2 = get_BoundaryInfo()->get_CodeC().decode(Edge.v2);
        int Min_X = get_BoundaryInfo()->getStartCoordinate().get_x();
        int Min_Y = get_BoundaryInfo()->getStartCoordinate().get_y();
        int Min_L = get_BoundaryInfo()->getStartCoordinate().get_layer_idx();

        unsigned long long X_1 = Decode1[0] + Min_X;
        unsigned long long X_2 = Decode2[0] + Min_X;
        unsigned long long Y_1 = Decode1[1] + Min_Y;
        unsigned long long Y_2 = Decode2[1] + Min_Y;
        unsigned long long L_1 = Decode1[2] + Min_L;
        unsigned long long L_2 = Decode2[2] + Min_L;

        ContestCoord coord1(X_1, Y_1, L_1);
        ContestCoord coord2(X_2, Y_2, L_2);
        routingSegmentUnderMinL.emplace_back(coord1, coord2);
    }
    return routingSegmentUnderMinL;
}

bool Route::SingleNetConnectivity(std::vector<ContestPin>& pinList, std::vector<ContestSegment>& segmentList, string netName) {

    bool check_result = true;

    std::vector<ContestCoord> key_coord_list;
    for (ContestPin& contest_pin : pinList) {
        key_coord_list.push_back(contest_pin.get_grid_coord());
    }
    if (!ContestUtil::passCheckingConnectivity(key_coord_list, segmentList)) {
        std::cout << "Disconnected Net: " << netName << std::endl;
        check_result = false;
    }

    return check_result;
}

} // namespace ieda_contest
